# -*- coding: utf-8 -*-
"""
Created on Fri Apr 24 10:42:09 2015

@author: hc
"""
'''
Python天天美味(32) - python数据结构与算法之堆排序 




1. 选择排序

选择排序原理是先选出最小的数，与第一个数交换，然后从第二个数开始再选择最小的数与第二个数交换，……
'''

def selection_sort(data):
    for i in range(len(data) - 1):
        min = data[i]
        k = i
        for j in range(i, len(data)):
            if data[j] < min:
                min = data[j]
                k = j
        if i <> k:
            data[i], data[k] = data[k], data[i]



'''
2. 堆排序

堆排序的原理将数组调整成堆，然后将堆顶元素与最后一个元素交换，然后将最后一个节点剔除出堆，再将剩下的数组调整成堆，然后再交换堆顶元素与最后一个元素……
'''

def heap_adjust(data, s, m):
    if 2 * s > m:
        return
    temp = s - 1
    if data[2*s - 1] > data[temp]:
        temp = 2 * s - 1
    if 2 * s <= m - 1 and data[2*s] > data[temp]:
        temp = 2 * s
    if temp <> s - 1:
        data[s - 1], data[temp] = data[temp], data[s - 1]
        heap_adjust(data, temp + 1, m)
def heap_sort(data):
    m = len(data) / 2
    for i in range(m, 0, -1):
        heap_adjust(data, i, len(data))
    data[0], data[-1] = data[-1], data[0]
    for n in range(len(data) - 1, 1, -1):
        heap_adjust(data, 1, n)
        data[0], data[n - 1] = data[n - 1], data[0]



import random
import datetime
import copy



def sort_perfmon(sortfunc, data):
    sort_data = copy.deepcopy(data)
    t1 = datetime.datetime.now()
    sortfunc(sort_data)
    t2 = datetime.datetime.now()
    print sortfunc.__name__, t2 - t1
    #print sort_data

data = [random.randint(0, 65536) for i in range(2000)]
#print data
sort_perfmon(selection_sort, data)
sort_perfmon(heap_sort, data)
'''
3. 效率

堆排序的效率还是蛮高的，结果如下：


selection_sort 0:00:02.219000
 heap_sort 0:00:00.157000
 
'''